package leetcode;

import util.DoubleListNode;

import java.util.HashMap;

/**
 * @Project : algorithm-learning-java
 * @Package : leetcode
 * @Author : Ruoyu Wang
 * @User : Momenta
 * @DateTime : 2024/1/19 10:34
 */
public class Q0146 {
    HashMap<Integer, Integer> data;
    HashMap<Integer, DoubleListNode> map;
    DoubleListNode head;
    DoubleListNode tail;
    int capacity;

    //    public LRUCache(int capacity) {
    public Q0146(int capacity) {
        data = new HashMap<>(capacity);
        map = new HashMap<>(capacity);
        head = new DoubleListNode(-1);
        tail = new DoubleListNode(-1);
        head.next = tail;
        tail.pre = head;
        this.capacity = capacity;
    }

    public int get(int key) {
        if (!data.containsKey(key)) return -1;
        DoubleListNode p = map.get(key);

        // 删除节点
        p.pre.next = p.next;
        p.next.pre = p.pre;
        // 头插插入节点
        p.next = head.next;
        p.pre = head;
        p.next.pre = p;
        p.pre.next = p;

        return data.get(key);
    }

    public void put(int key, int value) {
        if (data.containsKey(key)) {
            data.put(key, value);
            DoubleListNode p = map.get(key);

            p.pre.next = p.next;
            p.next.pre = p.pre;
            p.next = head.next;
            p.pre = head;
            p.next.pre = p;
            p.pre.next = p;
        } else {
            if (data.size() >= capacity) {
                DoubleListNode tmp = tail.pre;
                data.remove(tmp.val);
                map.remove(tmp.val);
                tmp.pre.next = tmp.next;
                tmp.next.pre = tmp.pre;
            }
            DoubleListNode p = new DoubleListNode(key);
            p.pre = head;
            p.next = head.next;
            p.next.pre = p;
            p.pre.next = p;
            data.put(key, value);
            map.put(key, p);
        }
    }
}
